package leetcode.offer_two_special.linked;

import java.util.LinkedList;

/**
 * @author mazouri
 * @create 2021-09-07 16:41
 */
public class _26_reorderList {
    public void reorderList1(ListNode head) {
        if (head == null) return;
        LinkedList<ListNode> deque = new LinkedList<>();

        ListNode node = head;
        while (node != null) {
            deque.add(node);
            node = node.next;
        }

        while (!deque.isEmpty()) {
            ListNode prev = deque.pollFirst();
            ListNode next = deque.pollLast();
            prev.next = next;

            if (next == null) return;
            next.next = deque.peekFirst();
        }
    }

    public void reorderList(ListNode head) {
        if (head == null) return;

        //先分割链表  先通过快慢指针找到中间节点
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode mid = slow.next;
        //分割，否则成环
        slow.next = null;
        //反转slow后面的节点 pre 头结点
        ListNode head2 = reverse(mid);
        //合并
        merge(head, head2);
    }

    private ListNode reverse(ListNode head) {
        ListNode pre = null;
        ListNode next = null;

        while (head!=null){
            //在head改变next时保存一下
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }


    private void merge(ListNode l1, ListNode l2) {
        while (l1 != null && l2 != null) {
            ListNode nextL1 = l1.next;
            ListNode nextL2 = l2.next;
            l1.next = l2;
            l2.next = nextL1;
            l1 = nextL1;
            l2 = nextL2;
        }
    }
}
